/**
 * 621. 任务调度器
 * https://leetcode-cn.com/problems/task-scheduler/
 */
public class Solutions_621 {
    public static void main(String[] args) {
        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
        int n = 2;  // output: 8

//        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
//        int n = 0;  // output: 6

//        char[] tasks = {'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//        int n = 2;  // output: 16

//        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E'};
//        int n = 2;  // output: 12

        int result = leastInterval(tasks, n);
        System.out.println(result);
    }

    /**
     * 解题思路：（贪心思路）
     * 存在规律：
     * 1. 调度时间由最大的出现次数决定
     * 2. 最大的出现次数可能有多个
     * 3. 推理公式：(最大出现次数) * (限制数n + 1) + 最大出现次数的数量
     * 4. 如果通过公式计算得到的最短时间，小于 tasks.length，那么结果就是 tasks.length
     */
    public static int leastInterval(char[] tasks, int n) {
        if (tasks == null) {
            return 0;
        }
        if (n == 0) {
            return tasks.length;
        }
        int[] counts = new int[26];
        for (char task : tasks) {
            counts[task - 'A'] ++;
        }
        // 找到最大出现次数
        int max = 0;
        for (int num : counts) {
            max = Math.max(max, num);
        }
        // 找到最大出现次数的任务数量
        int maxCount = 0;
        for (int num : counts) {
            maxCount += num == max ? 1 : 0;
        }
        // 计算公式
        // n + 1：即一组任务链中，可以执行 n + 1 个任务（任务 A 执行了，再过 n 个时间后，又可以执行 A）
        // max - 1：共有 max - 1 组任务，需要冷却
        // maxCount：最后执行的一组（该组就不需要冷却时间了）
        int res = (max - 1) * (n + 1) + maxCount;
        // 计算的最短时间，不会短于任务的数量（一个任务需要一个单位时间）
        return Math.max(res, tasks.length);
    }
}
